package com.caochenlei.graph;

import java.util.Stack;

public class DepthFirstOrder {
    private boolean[] marked;                   //索引代表顶点，值表示当前顶点是否已经被搜索
    private Stack<Integer> reversePost;         //使用栈，存储顶点序列

    public DepthFirstOrder(Digraph G) {
        this.marked = new boolean[G.size()];    //初始化marked数组
        this.reversePost = new Stack<>();       //初始化reversePost栈

        for (int v = 0; v < G.size(); v++) {
            if (!marked[v]) {                   //判断当前v顶点有没有被搜索过
                dfs(G, v);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
    }

    private void dfs(Digraph G, int v) {        //使用深度优先搜索找出G图中顶点v的所有相通顶点
        marked[v] = true;                       //把v顶点标识为已搜索
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                dfs(G, w);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
        reversePost.push(v);                    //让v顶点进栈
    }

    //获取顶点线性序列
    public Stack<Integer> reversePost() {
        return reversePost;
    }
}
